import java.util.List;

public class Test {
    public ListNode head;
    public void create(){
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(11);
        ListNode listNode3 = new ListNode(12);
        ListNode listNode4 = new ListNode(15);
        ListNode listNode5 = new ListNode(18);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        head = listNode1;

    }
//    public ListNode ReverseList(ListNode head) {
//        // Stack<ListNode> stack = new Stack<>();
//        // while (head != null){
//        //     stack.push(head);
//        //     head = head.next;
//        // }
//        // if (stack.isEmpty()){
//        //     return null;
//        // }
//        // ListNode node = stack.pop();
//        // ListNode dummy = node;
//        // while (!stack.isEmpty()){
//        //     ListNode tempNode = stack.pop();
//        //     node.next = tempNode;
//        //     node = node.next;
//        // }
//        // node.next = null;
//        // return dummy;
//
//        if (head == null){
//            return null;
//        }
//        ListNode pre = null;
//        ListNode next = null;
//        while (head != null){
//            next = head.next;
//            head.next = pre;
//            pre = head;
//            head = next;
//        }
//        return pre;
//
//
//    }
//
//    public ListNode Merge(ListNode list1,ListNode list2) {
//        // if (list1 == null){
//        //     return list2;
//        // }else if (list2 == null){
//        //     return list1;
//        // }
//        // if (list2.val > list1.val){
//        //     list1.next = Merge(list1.next,list2);
//        //     return list1;
//        // }else{
//        //     list2.next = Merge(list1,list2.next);
//        //     return list2;
//        // }
//        ListNode dummy = new ListNode(0);
//        ListNode res = dummy;
//        while (list1 != null && list2 != null) {
//            if (list1.val >= list2.val) {
//                dummy.next = list2;
//                list2 = list2.next;
//                dummy = dummy.next;
//            } else if (list1.val < list2.val) {
//                dummy.next = list1;
//                list1 = list1.next;
//                dummy = dummy.next;
//            }
//        }
//        if (list1 != null) {
//            dummy.next = list1;
//        }
//        if (list2 != null) {
//            dummy.next = list2;
//        }
//        return res.next;
//    }
//
//    public void dispiay(){
//        ListNode cur = head;
//        while (cur != null){
//            System.out.println(cur.val + " ");
//            cur = cur.next;
//        }
//        System.out.println();
//    }
//
//    public boolean contains(int key){
//        ListNode cur = head;
//
//        while (cur != null){
//
//            if (cur.val == key){
//
//                return true;
//
//            }
//
//            cur = cur.next;
//
//        }
//
//        return false;
//    }
//
//    public int size(){
//        ListNode cur = head;
//        int count = 0;
//        while (cur != null){
//            count++;
//            cur = cur.next;
//        }
//        return count;
//    }
//
//    public void addFirst(int data){
//        ListNode node = new ListNode(data);
//        node.next = head;
//        head = node;
////        if (head == null){
////            head = node;
////        }else {
////            node.next = head;
////            head = node;
////        }
//    }
//
//    public void addLast(int data){
//        ListNode node = new ListNode(data);
//        if (head == null){
//            head = node;
//        }else{
//            ListNode cur = head;
//            while (cur.next != null){
//                    cur = cur.next;
//            }
//        }
//        cur.next = node;
//    }
//
//    public ListNode findIndex(int index){
//        ListNode cur = head;
//        while (index-1 != 0){
//            cur = cur.next;
//            index--;
//        }
//        return cur;
//    }
//    public void addIndex(int index,int data){
//        if (index < 0 || index > size()){
//            System.out.println();
//            return;
//        }
//        if (index == 0){
//            addFirst(data);
//            return;
//        }
//        if (index == size()){
//            addLast(data);
//            return;
//        }
//        ListNode cur = findIndex(index);
//        ListNode node = new ListNode(data);
//        node.next = cur.next;
//        cur.next = node;
//
//    }
//
//    public ListNode searchNode(int key){
//        ListNode cur = head;
//        while (cur.next != null){
//            if (cur.next.val == key) {
//                return cur;
//            }
//            cur = cur.next;
//
//        }
//        return null;
//    }
//    public void remove(int key){
//        if (head == null){
//            return;
//        }
//        if (head.val == key){
//            head = head.next;
//            return;
//        }
//        ListNode cur = searchNode(key);
//        if (cur == null){
//            return;
//        }
//        ListNode del = cur.next;
////        while (cur.next != null){
////            if (cur.next.val == key){
////                cur.next = cur.next.next;
////                return;
////            }else {
////                cur = cur.next;
////            }
////        }
//        cur.next = del.next;
//    }
//
//    public void removeAllkey(int key){
//        if (head == null){
//            return;
//        }
//        ListNode prev = head;
//        ListNode cur = prev.next;
//        while (cur != null){
//            if (cur.val == key){
//                prev.next = cur.next;
//                cur = cur.next;
//            }else {
//                prev = cur;
//                cur = cur.next;
//            }
//        }
//        if (head.val = key){
//            head = head.next;
//        }
//        return head;
//
//
//
//    }
//
//    public void clear(){
//        while (head != null){
//            ListNode curNext = head.next;
//            head.next = null;
//            head = curNext;
//        }
//    }
//}
}
class ListNode{
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

